from typing import List


class Solution(object):
    # 找第一个
    def trap(self, height: List[int]) -> int:
        n = len(height)
        stack = []
        res = 0
        i = 0
        while i < n:
            if stack == [] or height[i] <= height[stack[-1]]:
                stack.append(i)
                i += 1
            else:
                i_ = stack.pop()
                if stack == []: continue
                h = min(height[stack[-1]], height[i]) - height[i_]
                res += h * (i-stack[-1]-1)
        return res
